/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var searchInsert = function (nums, target) {
    let left = 0
    let right = nums.length - 1
    let mid = Math.floor(nums.length / 2)
    while (left <= right) {
        if (target > nums[mid]) {
            left = mid + 1
        } else if (target < nums[mid]) {
            right = mid - 1
        } else {
            return mid
        }
        mid = Math.floor(right - (right - left) / 2)
    }
    // 如果没有找到target
    // target比最小的还要小
    if (target < nums[0]) {
        return 0
    }
    // target比最大的还要大
    else if (target > nums[nums.length + 1]) {
        return nums.length
    } 
    // target在中间
    else {
        return mid + 1
    }
};